import java.util.*;

//第一种:自上向下
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if (triangle.isEmpty()) return 0;
        ArrayList<ArrayList<Integer>> minPathSum = new ArrayList<>(triangle);
        minPathSum.get(0).set(0,triangle.get(0).get(0));
        for (int i = 1; i < triangle.size(); i++) {
            int curSum = 0;
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    curSum = minPathSum.get(i-1).get(0);
                } else if (j == i) {
                    curSum = minPathSum.get(i-1).get(j-1);
                } else {
                    curSum = Math.min(minPathSum.get(i-1).get(j),
                                      minPathSum.get(i-1).get(j-1));
                }
                minPathSum.get(i).set(j,triangle.get(i).get(j)+curSum);
            }
        }
        int len = triangle.size();
        int allMin = minPathSum.get(len-1).get(0);
        for(int i = 1; i < len; i++){
            allMin = Math.min(allMin,minPathSum.get(len-1).get(i));
        }
        return allMin;
    }
}

//第二种:自下向上
import java.util.*;
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if (triangle.isEmpty()) return 0;
        ArrayList<ArrayList<Integer>> minPathSum = new ArrayList<>(triangle);
        int len = minPathSum.size();
        for(int i = len-2; i >= 0; i--){
            for(int j = 0; j <= i; j++){
                int curSum = Math.min(triangle.get(i+1).get(j),
                triangle.get(i+1).get(j+1))+triangle.get(i).get(j);
                minPathSum.get(i).set(j,curSum);
            }
        }
        return minPathSum.get(0).get(0);
    }
}